#include <vector>
#include <deque>

using namespace std;

class Solution
{
public:
    vector<int> maxInWindows(vector<int> &nums, int k)
    {
        vector<int> ret;
        deque<int> q;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (!q.empty() && i - q.front() >= k)
            {
                q.pop_front();
            }
            while (!q.empty() && nums[q.back()] < nums[i])
            {
                q.pop_back();
            }
            q.push_back(i);
            if (i >= k - 1)
            {
                ret.push_back(nums[q.front()]);
            }
        }
        return ret;
    }
};